package ZuoChengYun.P4;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import javax.swing.*;
import java.util.Arrays;


/**
 * 荷兰国旗问题
 * (1)快速排序
 * 给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，
 * 大于num的数放在数组的右边。要求额外空间复杂度0(1)，时间复度0(N)
 *
 * (2)
 * 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，
 * 等于num的数放在数组的中间，大于num的数放在数组的右边。
 * 要求额外空间复杂度0(1)，时间复杂度0(N)
 * @author Knife
 */
public class QuickSort01 {
    public static void main(String[] args) {
        int num = 5;
        int [] arr = new int[]{3,8,9,5,4,5,4,6,2,8,1,3};
        System.out.println(Arrays.toString(arr));
        partition01(num, arr);
    }

    /**
     * 比num小的在左边，比num大的在右边
     * @param num
     * @param arr
     */
    private static void partition(int num, int[] arr) {
        int j = -1;
        for (int i = 0; i <= arr.length-1; i++) {
            if (arr[i] <= num){
                swap(arr,++j,i);
                System.out.println(i+"轮进行的"+Arrays.toString(arr));
            }
        }
        System.out.println("最终的排序数组"+Arrays.toString(arr));
    }

    /**
     * 比num小的在左边，等于num的在中间，大于num的在右边
     * @param num
     * @param arr
     */
    private static void partition01(int num, int[] arr){
        int i = 0;
        int j = arr.length;
        int k = -1;
        while (i<j){
            if (arr[i] < num){
              swap(arr,i++,++k);
            } else if(arr[i] > num) {
                swap(arr,i,--j);
            } else if(arr[i] == num) {
                i++;
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("最终的排序数组"+Arrays.toString(arr));
    }

    public static void swap(int[] arr,int i,int j){
        int temp ;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

